package leetcode.doublepointer;
//876. 链表的中间结点
//19. 删除链表的倒数第 N 个结点
public class MiddleNode {


    public static void main(String[] args) {

    }

    public ListNode middleNode(ListNode head) {
        ListNode temp = head;
        int n =0;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;

        }
        if (length%2==0){
            n=length/2+1;
        }else {
            n = length/2;
        }
        ListNode res = head;
        for (int i =0;i<n;i++){
            res = res.next;
        }
        return res;

    }

    //转数组
    public ListNode middleNode2(ListNode head) {
        ListNode temp = head;
        ListNode[] f = new ListNode[100];  //大小自定义
        int index=0;
        while (temp!=null){
            f[index++]=temp;
            temp = temp.next;
        }
        return f[index/2];
    }

    //快慢指针
    public ListNode middleNode3(ListNode head) {
        ListNode fast= head;
        ListNode slow= head;
        while (fast!=null && fast.next!=null){
            fast= fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    public ListNode removeNthFromEnd(ListNode head, int n) {

        //定义一个虚拟头结点
        ListNode dummyHead =new  ListNode(0,head);
        ListNode temp = head;
        int length = 0;
        while (temp!=null){
            length++;
            temp = temp.next;
        }
        ListNode res = dummyHead;
        for (int i =0;i<length-n;i++){
            res = res.next;
        }
        res.next=res.next.next;

        return dummyHead.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

 class ListNode {
   int val;
   ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}